#include "binaryTree.h"
#include <stdlib.h>
#include <stdio.h>
SearchTree MakeEmpty(SearchTree T)
{
    if (T != NULL)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        //先序遍历释放整个二叉树
        free(T);
    }
    return NULL;
}
Position Find(ElementType X, SearchTree T)
{
    if (T == NULL)
    {
        return NULL;
    }

    if (X < T->Element)
    {
        //使用尾递归，这种递归方式很容易能被改写为循环或者goto。但是为了方便，我们将其写为尾递归的方式。
        //编译时，指定优化尾递归来防止递归可能造成的栈溢出。
        return Find(X, T->Left);
    }
    else if (X > T->Element)
    {
        return Find(X, T->Right);
    }
    else
    {
        return T;
    }
}
Position FindMin(SearchTree T)
{
    if (T == NULL)
    {
        return NULL;
    }
    else if (T->Left == NULL)
    {
        return T;
    }
    else
    {
        return FindMin(T->Left);
    }
}
Position FindMax(SearchTree T)
{
    //我们可以轻松地将尾递归改写为循环
    if (T != NULL)
    {
        while (T->Right != NULL)
        {
            T = T->Right;
        }
    }
    return T;
}

SearchTree Insert(ElementType X, SearchTree T)
{
    if (T == NULL)
    {
        //insert
        T = malloc(sizeof(struct TreeNode));
        if (T == NULL)
        {
            printf("malloc error\n");
            return NULL;
        }
        else
        {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    }
    else if (X < T->Element)
    {
        T->Left = Insert(X, T->Left);
    }
    else if (X > T->Element)
    {
        T->Right = Insert(X, T->Right);
    }

    return T;
}

//这种删除方法会使左子树逐渐变得比右子树更深
SearchTree Delete(ElementType X, SearchTree T)
{
    Position Tmp;
    if (T == NULL)
    {
        printf("element not found\n");
    }
    else if (X < T->Element)
    {
        T->Left = Delete(X, T->Left);
    }
    else if (X > T->Element)
    {
        T->Right = Delete(X, T->Right);
    }
    else if (T->Right && T->Left)
    {
        //有两个子树
        Tmp = FindMin(T->Right);
        T->Element = Tmp->Element;
        //这样做效率并不是很高，因为最小节点搜索了两次
        T->Right = DeleteMin(T->Right, &(T->Element));
    }
    else
    {
        Tmp = T;
        if (T->Left == NULL)
        {
            T = T->Right;
        }
        else if (T->Right == NULL)
        {
            T = T->Left;
        }
        free(Tmp);
    }

    return T;
}

//从T中删除最小的节点并且返回T地址
//最小节点值保存在min中
SearchTree DeleteMin(SearchTree T, ElementType *min)
{
    ElementType X;
    SearchTree tmp;
    if (T == NULL)
    {
        return NULL;
    }
    else if (T->Left == NULL)
    {
        tmp = T;
        X = T->Element;
        T = T->Right;
        free(tmp);
        *min = X;
        return T;
    }
    else
    {
        T->Left = DeleteMin(T->Left, min);
        return T;
    }
}

void printTab(SearchTree T, int tabLevel)
{
    int i = 0;

    if (T != NULL)
    {
        for (i = 0; i < tabLevel; i++)
        {
            printf("    ");
        }
        printf("%d\n", T->Element);
        printTab(T->Left, tabLevel + 1);
        printTab(T->Right, tabLevel + 1);
    }
}

void Print(SearchTree T)
{
    printTab(T, 0);
}